package com.linzm.leetcode.mid.exercises2_20230211;

/**
 * @Author zimingl
 * @Date 2023/2/13 21:58
 * @Description: 数组中的最长山脉
 * 把符合下列属性的数组 arr 称为 山脉数组 ：
 * arr.length >= 3
 * 存在下标 i（0 < i < arr.length - 1），满足
 * arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
 * arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
 * 给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。
 * <p>
 * 输入：arr = [2,1,4,7,3,2,5]
 * 输出：5
 * 解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。
 * 输入：arr = [2,2,2]
 * 输出：0
 * 解释：不存在山脉子数组。
 * 1 <= arr.length <= 104
 * 0 <= arr[i] <= 104
 *
 * 做法： 两个数组，左数组和右数组
 */
public class Demo8_845 {
    public static void main(String[] args) {
        int[] arr = {2, 1, 4, 7, 3, 2, 5, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0};
//        int[] arr = {2, 2, 2};
//        int[] arr = {0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0};
        Demo8_845 demo8_845 = new Demo8_845();
        int longestMountain = demo8_845.longestMountain2(arr);
        System.out.println(longestMountain);
    }

    private int longestMountain(int[] arr) {
        int left = 0;
        int leftLen = 0;
        int rightLen = 0;
        int flag1 = 0, flag2 = 0;
        int maxLen = -1;
        for (int i = 0; i < arr.length - 1; i++) {
            if ((rightLen != 0 && flag1 * flag2 < 0 && arr[i + 1] > arr[i]) || (i == arr.length - 2 && flag1 * flag2 < 0)) {
                if (i == arr.length - 1) {
                    maxLen = Math.max(maxLen, leftLen + rightLen + 2);
                }
                maxLen = Math.max(maxLen, leftLen + rightLen + 1);
                leftLen = 0;
                rightLen = 0;
                i = ++left;
                flag1 = flag2 = 0;
            }
            if (arr[i + 1] > arr[i]) {
                leftLen++;
                flag1 = 1;
            }
            if (arr[i + 1] < arr[i] && flag1 == 1) {
                rightLen++;
                flag2 = -1;
            }
        }
        return maxLen == -1 ? 0 : maxLen;
    }

    private int longestMountain2(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int[] left = new int[n];
        for (int i = 1; i < n; ++i) {
            left[i] = arr[i - 1] < arr[i] ? left[i - 1] + 1 : 0;
        }
        int[] right = new int[n];
        for (int i = n - 2; i >= 0; --i) {
            right[i] = arr[i + 1] < arr[i] ? right[i + 1] + 1 : 0;
        }
        // left [0, 0, 1, 2, 0, 0, 1, 0, 1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
        // right [1, 0, 0, 2, 1, 0, 1, 0, 0, 0, 0, 0, 5, 4, 3, 2, 1, 0]
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (left[i] > 0 && right[i] > 0) {
                ans = Math.max(ans, left[i] + right[i] + 1);
            }
        }
        return ans;
    }
}
